/*
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <hash_map>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

int climbStairs(int n) {
	int *re=(int *)malloc(sizeof(int)*(n+2));
	memset(re,0,sizeof(int)*(n+2));
	re[0]=1;
	for(int i=0;i<n;i++){
		re[i+1]+=re[i];
		re[i+2]+=re[i];
	}
	return re[n];
}
int main(){
	cout<<climbStairs(3);
	cout<<endl;
	system("pause");
	return 0;
}
*/